package algorithm.shipinke;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

import static java.lang.Integer.MAX_VALUE;

/**
 * 你有三种硬币，分别面值2元，5元和7元，每种硬币都有足够多。买一本书需要27元。如何用最少的硬币组合正好付清，不需要对方找钱？
 */

public class MinCoinComb {
    public static int calculateMinCoin(int n) throws IllegalArgumentException {
        if (n < 0) {
            throw new IllegalArgumentException("输入违法！");
        } else {
            List<Integer> initialState = new ArrayList<Integer>(Arrays.asList(0, MAX_VALUE, 1, MAX_VALUE, 2, 1, MAX_VALUE, 1));

            while (n > initialState.size() - 1) {
                int wait2AddIndex = initialState.size();
                int fn_2 = initialState.get(wait2AddIndex-2);
                int fn_5 = initialState.get(wait2AddIndex-5);
                int fn_7 = initialState.get(wait2AddIndex-7);
                int min = Collections.min(Arrays.asList(fn_2, fn_5, fn_7));
                if (min == MAX_VALUE) {
                    initialState.add(MAX_VALUE);
                } else {
                    initialState.add(min + 1);
                }
            }
            return initialState.get(n);
        }
    }

    public static void main(String[] args) {
        System.out.println(calculateMinCoin(220));
        int[] a = {1,2,3};
        System.out.println(Arrays.equals(a, new int[]{1,2,3}));
        new ArrayList<String>(3);
    }
}
